package br.com.vm.dijkstra;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

import br.com.vm.dijkstra.graph.Aresta;
import br.com.vm.dijkstra.graph.Vertice;

public class Dijkstra {
	public void processarCaminhos(Vertice origem) {
		origem.distanciaMinima = 0.;
		PriorityQueue<Vertice> filaVertices = new PriorityQueue<Vertice>();
		filaVertices.add(origem);

		while (!filaVertices.isEmpty()) {
			Vertice u = filaVertices.poll();
			if (u.adjacentes != null) {
				// Visit each edge exiting u
				for (Aresta e : u.adjacentes) {
					Vertice v = e.destino;
					double distancia = e.distancia;
					double distanceThroughU = u.distanciaMinima + distancia;
					if (distanceThroughU < v.distanciaMinima) {
						filaVertices.remove(v);

						v.distanciaMinima = distanceThroughU;
						v.verticeAnterior = u;
						filaVertices.add(v);
					}
				}
			}
		}
	}

	public List<Vertice> obterMenorCaminho(Vertice destino) {
		List<Vertice> path = new ArrayList<Vertice>();
		for (Vertice vertice = destino; vertice != null; vertice = vertice.verticeAnterior)
			path.add(vertice);

		Collections.reverse(path);
		return path;
	}

	public static void main(String[] args) {
		Vertice a = new Vertice("A");
		Vertice b = new Vertice("B");
		Vertice c = new Vertice("C");
		Vertice d = new Vertice("D");
		Vertice e = new Vertice("E");

		// for A
		List<Aresta> adjacentes = new ArrayList<Aresta>();
		adjacentes.add(new Aresta(b, 10));
		adjacentes.add(new Aresta(c, 20));
		a.setAdjacentes(adjacentes);

		// for B
		adjacentes = new ArrayList<Aresta>();
		adjacentes.add(new Aresta(d, 15));
		adjacentes.add(new Aresta(e, 50));
		b.setAdjacentes(adjacentes);

		// for C
		adjacentes = new ArrayList<Aresta>();
		adjacentes.add(new Aresta(d, 30));
		c.setAdjacentes(adjacentes);

		// for D
		adjacentes = new ArrayList<Aresta>();
		adjacentes.add(new Aresta(e, 30));
		c.setAdjacentes(adjacentes);

		// Vertice[] vertices = { a, b, c, d, e };

		new Dijkstra().processarCaminhos(a);

		List<Vertice> path = new Dijkstra().obterMenorCaminho(d);

		System.out.println("Path: " + path);
		System.out.println("Distance to " + a + ": " + d.distanciaMinima);

		// for (Vertice v : vertices) {
		// System.out.println("Distance to " + v + ": " + v.minDistance);
		// List<Vertice> path = getShortestPathTo(v);
		// System.out.println("Path: " + path);
		// }
	}
}
